package SlidingWindow;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-10-29
 * Time: 21:57
 */
/*
* 这道题做的血液沸腾2h太爽了*/
class Solution9 {
    public String minWindow(String ss, String tt) {
        //先把要找的字符tt转化为数组并放到哈希表里
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128];
        int kind = 0;//统计tt字符串中有多少种字符
        for(char ch : t){
            hash1[ch]++;
            if(hash1[ch] == 1){
                kind++;
            }
        }

        //同样把字符ss转化为数组
        char[] s = ss.toCharArray();
        int[] hash2 = new int[128];
        int len = Integer.MAX_VALUE;
        int left = 0 , right = 0 , begin = -1 ;

        for(int count = 0; right < s.length ; right++){
            //进窗口
            char in = s[right];
            hash2[in]++;
            //判断如果直接判断两个哈希表非常耗费时间引入count
            if(hash1[in] == hash2[in]){
                count++;
            }


            //更新结果(如果种类一直相同，那就一直出窗口所以用while)
            while(count == kind){
                if(right - left + 1 < len){
                    begin = left;
                    len = right-left+1;
                }

                //出窗口
                char out = s[left++];
                if(hash2[out] == hash1[out] ){//考虑两种情况，出的是有效字符还是无效字符
                    count--;
                }
                hash2[out]--;

            }

        }
        //for循环走完了一直进不去while循环，返回空字符串
        if(len == Integer.MAX_VALUE){
            return new String();
        }else{
            String ret = ss.substring(begin,begin+len);
            return ret;
        }


    }
}
public class Test9 {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        Solution9 test = new Solution9();
        test.minWindow(s,t);
    }
}
